package io.github.handyang.algorithms.sort;

import java.util.ArrayList;

public class MyLSDRadixSortAlgorithms implements SortAlgorithms {
    @Override
    public void sort(int[] arr) {
        int maxLen = maxLen(arr);

        ArrayList[] buckets = new ArrayList[10];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList();
        }

        int radix = 1;
        for (int i = 0; i < maxLen; i++) {
            for (int item : arr) {
                buckets[(item / radix) % 10].add(item);
            }

            radix *= 10;
            int index = 0;
            for (ArrayList<Integer> bucket : buckets) {
                for (Integer item : bucket) {
                    arr[index++] = item;
                }

                bucket.clear();
            }
        }
    }

    private int maxLen(int[] arr) {
        int max = arr[0];
        for (int item : arr) {
            if (item > max) max = item;
        }

        int i = 1;
        while (max >= 10) {
            i++;
            max /= 10;
        }

        return i;
    }
}
